Nawiasy

Limit pamięci: 32 MB

Wyrażeniem nawiasowym nazwiemy niepusty ciąg składający się z nawiasów otwierających i zamykających. Powiemy, że wyrażenie nawiasowe jest poprawne, jeżeli każdy nawias otwierający można sparować z nawiasem zamykającym, występującym po nim, tak aby ciąg nawiasów znajdujących się pomiędzy nimi również był poprawnym ciągiem nawiasowym.

Na przykład (()())() jest poprawnym wyrażeniem nawiasowym, ale )( i ()( już poprawne nie są.

Bajtazar w swojej pracy naukowej skorzystał z programu wypisującego pewne poprawne wyrażenie nawiasowe , mające kluczowe znaczenie dla jego badań. Niestety, słowo to zaginęło w gąszczu innych nawiasów, które przez przypadek mogły być wypisane zarówno przed nim, jak i po nim. Bajtazar otrzymał więc słowo nawiasowe, które zawiera w sobie jako spójny fragment szukane słowo , jednak nie wie, gdzie się ono zaczyna i gdzie kończy.

Zrozpaczony, poprosił Ciebie o pomoc w wyznaczeniu wszystkich możliwych położeń poprawnych słów nawiasowych w otrzymanym słowie. Ma bowiem nadzieję, że jest ich niewiele ...

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą długość słowa, które odczytał Bajtazar. W drugim wierszu znajduje się nawiasów (bez odstępów) - jest to odczytane słowo nawiasowe.

Możesz założyć, że w testach wartych przynajmniej punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą oznaczającą liczbę fragmentów odczytanego słowa, które są poprawnymi słowami nawiasowymi.

Przykład

Dla danych wejściowych:

10
)(())()(()

poprawną odpowiedzią jest:

5